1. Field of the Invention
The present invention relates to random number generators and in particular to random number generators that can be used in connection with cryptographic applications.
2. Description of the Related Art
There are many fields in the art where random numbers are needed. Some of these fields, for example, are simulations where random numbers are used so as to be able to simulate deterministic physical processes. By randomly changing various values of the simulation one can achieve that a simulation method which is “trapped” in a local maximum or minimum, becomes detached from this local maximum or minimum so as to perhaps succeed, eventually, in finding the global maximum or the global minimum.
Random numbers are also used for testing hardware or software. These random numbers are needed, if it is not possible to test all occurring digital signal vectors, to examine the system's performance/behavior in random signal vectors that have not been generated systematically.
A very important application for random number generators is cryptography. Modern cryptography methods are based on a random key which should be as long as the data to be encrypted. Their security is directly related to the randomness of the key. In general, key generation for cryptographic schemes should be based on random numbers, since random numbers are the only thing a potential attacker cannot guess. This is true both for symmetrical and for asymmetrical encryption methods. In most symmetrical encryption methods, sequences of randomly generated bits are used as keys. In asymmetric encryption methods, the structure of the keys is often more complex. For example, RSA keys are based on high prime numbers that must remain secret. Random numbers should be used for generating the prime numbers. They can be used, for example, to provide the starting number for a sequential search for prime numbers.
Further applications of random numbers as well as a general overview of the generation of random numbers are disclosed in “A High Quality Physical Random Number Generator”, M. Dichtl and N. Janssen, Eurosmart Security Conference —Proceedings, Marseille, 2000, pages 277–278.
U.S. Pat. No. 4,855,690 describes a random number generator which uses, as a basic parameter, samples of an output signal of an oscillator with variable frequency. Such a circuit is shown in FIG. 3. The random number generator includes an analog oscillator 300, a voltage-controlled digital oscillator 400, a logic circuit 500 which typically includes a flip-flop circuit, a clock oscillator 600, a central processing unit (CPU) 700, and a sampling device 800. Analog oscillator 300 generates a triangular signal which is fed into a control input of voltage-controlled digital oscillator 400. The sampling of the output signal of the voltage-controlled digital oscillator is effected by putting the sampling device in a sampling state by means of logic circuit 500. In the sampling state the current value of the output signal of VCO 400 is present at the output of the random number generator. In the idle state of the switching device, however, a signal is present at the output. The sampling device is then put into the sampling state by the logic circuit if two conditions are met. The first condition is that CPU 700 outputs an enable signal. The second condition is that the output signal of the clock oscillator exhibits a certain state, for example a rising edge. A chain of random output values is then generated when the CPU outputs the enable signal, which will be the case once the CPU has received the command to activate, i.e. to switch on, the random number generator. The frequency of the random values at the output of the random number generator corresponds exactly to the frequency of clock oscillator 600, since logic circuit 500 is arranged such that it drives, whenever the output signal of the clock oscillator is in a certain state, the sampling device 800 in such a manner that it supplies a sample at the output. However, this means at the same time that the frequency of the output values and/or temporal control of the sampling is independent of the frequency of analog oscillator 300 or of digital VCO 400. The output samples always exhibit the same frequency as the clock oscillator, it no longer being possible to determine the frequency of analog oscillator 300 and/or the frequency of digital VCO 400 in the sequence of samples at the output of the random number generator.
Not in all cases is it desirable that the frequency of the output samples be independent of the frequency of the analog oscillator and/or the voltage-controlled digital oscillator. The security of some applications, e.g. with payment cards, is jeopardized when the oscillator serving as a random source is sampled too often, so that the values obtained are strongly correlated. Such too frequent sampling might be intentionally caused by an attacker if he or she succeeds in increasing the frequency of clock oscillator 600. This threat is realistic in particular with chip card systems, as these frequently work with a clock which is fed in externally.
When the frequencies of oscillators 300 and 400 are raised, the sampling frequency, on the other hand, can also be raised, so that the existing resources are better utilized due to the higher data rate of the random number generation.